package Bi_Tree.level_traversal;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/*
* 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
* */
public class lc116 {
    public Node_ connect(Node_ root) {
        List<List<Node_>> list=new ArrayList<>();
        Queue<Node_> queue=new LinkedList<>();
        Node_ node=root;
        queue.offer(node);
        while (!queue.isEmpty()){
            List<Node_> smalllist=new ArrayList<>();
            int len= queue.size();
            while (len>0){
                node=queue.poll();
                smalllist.add(node);
                if(node.left!=null) queue.offer(node.left);
                if(node.right!=null) queue.offer(node.right);
                len--;
            }
            list.add(smalllist);
        }
        for (int i = 0; i < list.size() ; i++) {
            List<Node_> s_list=list.get(i);
            if(s_list.size()==1){
                s_list.get(0).next=null;
            }else if(s_list.size()==2){
                s_list.get(0).next=s_list.get(1);
            } else if (s_list.size()>=3) {
                Node_ pre=s_list.get(0);
                Node_ p=s_list.get(1);
                for (int j = 0; j <s_list.size()-1 ; j++) {
                    pre.next=p;
                    pre=p;
                    if(2+j<s_list.size()){
                        p=s_list.get(2+j);
                    }else{
                        p=null;
                    }
                }
            }
        }
        return root;

    }
}

class Node_ {
    public int val;
    public Node_ left;
    public Node_ right;
    public Node_ next;

    public Node_() {}

    public Node_(int _val) {
        val = _val;
    }

    public Node_(int _val, Node_ _left, Node_ _right, Node_ _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
}
